package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-27 11:48
 */
public class 题库_0062_不同路径 {

  static
  class Solution {
    public int uniquePaths(int m, int n) {
      if (m == 1 || n == 1) {
        return 1;
      }
      int min = Math.min(m, n);
      int max = Math.max(m, n);
      int[] dp = new int[min];
      for (int i = 0; i < min; ++i) {
        dp[i] = 1;
      }
      for (int i = 1; i < max; ++i) {
        for (int j = 1; j < min; ++j) {
          dp[j] += dp[j - 1];
        }
      }
      return dp[min - 1];
    }
  }

}
